package app_demo.lru;


import java.util.HashMap;
import java.util.Map;

/**
 * @Description 146. LRU 缓存
 * @Author Firenut
 * @Date 2023-02-12 00:43
 */
class LRUCache {
    // HashMap好像自己会扩容... 但是没有影响，因为size()返回的是有效k-v的个数
    // 如何判断哪个key-value是最近最少被使用?要加一些字段?
    // 使用双向链表，越靠近头结点表示最近被使用,越靠近尾结点表示越久未被使用
    // 查询结点的时候需要更新结点的位置到头结点(此过程需要先将该结点断开连接,然后插入到头结点)
    // 插入结点的时候,如果结点存在需要覆盖val值并将该结点移动到头结点位置
    // 使用Map是为了在get的时候可以用O(1)的时间 快速获取到val
    Map<Integer, LinkNode> map;

    LinkNode head;
    LinkNode tail;
    int size;

    class LinkNode {
        int key;  //方便删除结点的时候通过key定位到Hash表,不然在删除链表之后没法快速定位到哈希表的k-v
        int val;
        LinkNode pre;
        LinkNode next;

        LinkNode() {
        }

        LinkNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    // 设置头尾结点是为了方便后续对链表的操作
    public LRUCache(int capacity) {
        // 初始化HashMap
        this.map = new HashMap<>(capacity);
        this.size = capacity;
        // 初始化头尾结点
        head = new LinkNode();
        tail = new LinkNode();
        head.next = tail;
        // head.pre=null;
        tail.pre = head;
        // tail.next=null;
    }

    // 获取该结点,如果存在返回该结点值,删除该结点并插入到链表头部
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        LinkNode node = map.get(key);
        // map.remove(key);
        remove(node);
        addFirst(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (!map.containsKey(key)) {//不包含该结点
            LinkNode node = new LinkNode(key, value);
            addFirst(node);     // 添加到双向链表头部
            map.put(key, node); // 添加到哈希表
            // 如果插入后 结点数大于设定容量，需要移除尾结点
            if (map.size() > this.size) {
                LinkNode del = tail.pre;
                map.remove(del.key); //从哈希表移除
                remove(del);    //从双向链表移除
            }
        } else {
            LinkNode node = map.get(key);
            node.val = value; // 修改该结点的val值
            remove(node);
            addFirst(node);
        }
    }

    // 移除指定结点
    void remove(LinkNode node) {
        node.pre.next = node.next;  // ***
        node.next.pre = node.pre;
    }

    // 从头部插入
    // 结点插入这块要搞清楚(先插入再断开)
    void addFirst(LinkNode node) {
        // node连接到head的下一个结点
        node.next = head.next;
        head.next.pre = node;

        // head连接node
        head.next = node;
        node.pre = head;
    }
}